package advanced.sorting;

import java.util.ArrayList;
import java.util.Scanner;


public class MergeSort {

    private ArrayList<String> StringList;


    public MergeSort(ArrayList<String> input)
    {
        StringList = new ArrayList<String>();
        for(int i=0; i<input.size(); i++)
        {
            StringList.add(input.get(i));
        }
    }

    public void sort()
    {

        StringList=mergeSort(StringList);

    }

    public ArrayList<String> mergeSort(ArrayList<String> whole)
    {
        ArrayList<String> left = new ArrayList<String>();
        ArrayList<String> right = new ArrayList<String>();
        int center;

        if(whole.size()==1)    
            return whole;
        else
        {
            center = whole.size()/2;
            // copy the left half of whole into the left.
            for(int i=0; i<center; i++)
            {
                    left.add(whole.get(i));
            }

            //copy the right half of whole into the new arraylist.
            for(int i=center; i<whole.size(); i++)
            {
                    right.add(whole.get(i));
            }

            // Sort the left and right halves of the arraylist.
            left  = mergeSort(left);
            right = mergeSort(right);


            // Merge the results back together.
            merge(left,right,whole);

        }
        return whole;
    }

    private void merge(ArrayList<String> left, ArrayList<String> right, 
            ArrayList<String> whole) {

        int leftIndex = 0;
        int rightIndex = 0;
        int wholeIndex = 0;


        // As long as neither the left nor the right arraylist has
        // been used up, keep taking the smaller of left.get(leftIndex)
        // or right.get(rightIndex) and adding it at both.get(bothIndex).
        while (leftIndex < left.size() && rightIndex < right.size())
        {
            if ((left.get(leftIndex).compareTo(right.get(rightIndex)))<0) 
            {
                whole.set(wholeIndex,left.get(leftIndex));
                leftIndex++;
            }
            else 
            {
                whole.set(wholeIndex, right.get(rightIndex));
                rightIndex++;
            }
            wholeIndex++;
        }

        ArrayList<String>rest;
        int restIndex;
        if (leftIndex >= left.size()) {
            // The left arraylist has been use up...
            rest = right;
            restIndex = rightIndex;
        }
        else {
            // The right arraylist has been used up...
            rest = left;
            restIndex = leftIndex;
        }

        // Copy the rest of whichever arraylist (left or right) was
        // not used up.
        for (int i=restIndex; i<rest.size(); i++) {
            whole.set(wholeIndex, rest.get(i));
            wholeIndex++;
        }
    }

    public void show()
    {
        System.out.println("Sorted:");
        for(int i=0; i< StringList.size();i++)
        {
            System.out.println(StringList.get(i));
        }

    }

    public static void main(String[] args) {
        ArrayList<String> input = new ArrayList<String>();
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter your text, type done for exit:");
        String strin = sc.nextLine();

        while(!strin.equals("done"))
        {
            input.add(strin);
            strin = sc.nextLine();
        }
        System.out.println("************************");
        MergeSort test = new MergeSort(input);
        test.sort();
        test.show();
    }

}
